package cn.z2huo.algorithm.sort.swapSort.quickSort;

//三数取中
public class SortQuick5 {
	//进行第一次排序，之后找到轴的位置后对得到的左小右大的数列分别再进行排序
	public void quickSort(int[] array, int low, int high) {
		int cenPos = 0;
		if(low<high) {
			if((high-low) > 10) {
				cenPos = parting(array, low, high);
				//空间优化，先对长度短的子序列进行排序，降低栈的深度
				if((high-cenPos) > (cenPos-low)) {
					quickSort(array,low,cenPos-1);
					quickSort(array,cenPos+1,high);
				}else {
					quickSort(array,cenPos+1,high);
					quickSort(array,low,cenPos-1);
				}
			}else {
				//insertSort(array, low, high);
			}
		}
	}
	
	//进行一次排序，改变中轴的位置，此方法运行完数组中轴左边的数都比轴数小，右边的都比它大
	public int parting(int[] array, int low, int high) {
		int right = high;
		int left = low;
		//初始轴的位置进行三数取中选取（中轴的位置有影响，采用不同的中轴位置，对算法会有改进）
		chooseCenPos(array, high, low);
		int cenPos = low;
		System.out.println("排序中轴的初始位置："+cenPos);
		int cenValue = array[cenPos];
		//该循环进行此方法的主要操作，左小右大的划分
		while(low<high) {
			while(low < high && array[high]>=cenValue && high>cenPos) {
				if(array[high] == array[cenPos]){  // 处理相等元素
					swap(array, right, high);
					right --;
				}
				high--;
			}
			if(low<high) {
				array[cenPos] = array[high];
				cenPos = high;
			}
			while(low < high && array[low]<=cenValue && low<cenPos) {
				if(array[low] == array[cenPos]) {	// 处理相等元素
					swap(array, left, low);
					left ++;
				}
				low++;
			}
			if(low<high) {
				array[cenPos] = array[low];
				cenPos = low;
			}
			printArray(array);
		}
		array[cenPos] = cenValue;
		
		printArray(array);
		System.out.println("以上排序中轴的最终位置 "+cenPos);
		//一遍左小右大的排序完成之后，返回最终轴的位置，为后面的操作创造条件
		return cenPos;
	}
	
	//该方法输出传入的数列
	public void printArray(int[] array) {
		for(int i=0; i<array.length; i++) {
			System.out.printf("%d ",array[i]);
		}
		System.out.println();
	}
	
	//三数取中，选择枢轴位
	public void chooseCenPos(int[] array, int high, int low) {
		int mid = (low + high)/2;
		if(array[low] > array[high]) {
			swap(array, low, high);
		}
		if(array[mid] > array[high]) {
			swap(array, mid, high);
		}
		if(array[mid] > array[low]) {
			swap(array, mid, low);
		}
	}
	
	public void swap(int[] array, int high, int low) {
		int temp = array[low];
		array[low] = array[high];
		array[high] = temp;
	}
	
	public static void main(String[] args) {
		int[] array = {11,13,2,34,55,9,44,122,32,2,9};
		SortQuick5 sq = new SortQuick5();
		
		sq.printArray(array);
		System.out.println("初始");
		sq.quickSort(array, 0, array.length-1);
		
		sq.printArray(array);
	}
}
